A second-order cellular automaton is a type of

reversible cellular automaton A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells s ...

(CA) invented by

Edward Fredkin Edward Fredkin (born October 2, 1934) is a distinguished career professor at Carnegie Mellon University (CMU), and an early pioneer of digital physics. Fredkin's primary contributions include work on reversible computing and cellular automata. ...

. Reprinted in . where the state of a cell at time depends not only on its neighborhood at time , but also on its state at time ..

General technique

In general, the evolution rule for a second-order automaton may be described as a function that maps the neighborhood of a cell to a

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...

on the states of the automaton. In each time step , for each cell of the automaton, this function is applied to the neighborhood of to give a permutation . Then, this permutation is applied to the state of cell at time , and the result is the state of the cell at time . In this way, the configuration of the automaton at each time step is computed from two previous time steps: the immediately previous step determines the permutations that are applied to the cells, and the time step before that one gives the states on which these permutations operate. The reversed time dynamics of a second-order automaton may be described by another second-order automaton with the same neighborhood, in which the function mapping neighborhoods to permutations gives the inverse permutation to . That is, on each possible neighborhood , and should be inverse permutations. With this reverse rule, the automaton described by function correctly computes the configuration at time from the configurations at time and . Because every second-order automaton can be reversed in this way, it follows that they are all reversible cellular automata, regardless of which function is chosen to determine the automaton rule.

For two-state automata

If a cellular automaton has only two states, then there are also only two possible permutations of states: the

identity permutation In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to its ...

that maps each state to itself, and the permutation that maps each state to the other state. We may identify these two permutations with the two states of the automaton. In this way, every second-order cellular automaton (defined by a function from neighborhoods to permutations) corresponds uniquely to an ordinary (first-order) cellular automaton, defined by a function directly from neighborhoods to states. Two-state second-order automata are symmetric under time reversals: the time-reversed dynamics of the automaton can be simulated with the same rule as the original dynamics. If we view the two states as

Boolean value In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in ...

s, this correspondence between ordinary and second-order automaton can be described simply: the state of a cell of the second-order automaton at time is the

exclusive or Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...

of its state at time with the state that the ordinary cellular automaton rule would compute for it.. See especially section 5.4 "Second-order cellular automata", pp. 238–240. This issue of Physica D was reprinted as . In fact, all two-state second-order rules may be produced in this way. The resulting second-order automaton, however, will generally bear little resemblance to the ordinary CA it was constructed from. Second-order rules constructed in this way are named by

Stephen Wolfram Stephen Wolfram (; born 29 August 1959) is a British-American computer scientist, physicist, and businessman. He is known for his work in computer science, mathematics, and theoretical physics. In 2012, he was named a fellow of the American Ma ...

by appending an "R" to the number or

Wolfram code Wolfram code is a widely used numbering system for one-dimensional cellular automaton rules, introduced by Stephen Wolfram in a 1983 paper and popularized in his book ''A New Kind of Science''. The code is based on the observation that a table spec ...

of the base rule.

Applications

Second-order automata may be used to simulate

billiard-ball computer A billiard-ball computer, a type of conservative logic circuit, is an idealized model of a reversible mechanical computer based on Newtonian dynamics, proposed in 1982 by Edward Fredkin and Tommaso Toffoli. Instead of using electronic signals li ...

s and the

Ising model The Ising model () (or Lenz-Ising model or Ising-Lenz model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent ...

ferromagnetism Ferromagnetism is a property of certain materials (such as iron) which results in a large observed magnetic permeability, and in many cases a large magnetic coercivity allowing the material to form a permanent magnet. Ferromagnetic materials ...

statistical mechanics In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...

.. They may also be used for

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

References

{{reflist Cellular automata